home *** CD-ROM | disk | FTP | other *** search
/ GFX Sensations 1 / Graphic Sensations - Volume 1.iso / tools / amiga / 3d_tools / irit40s.lha / Irit / cagd_lib / bspboehm.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-30  |  5.4 KB  |  151 lines
  1. /******************************************************************************
  2. * BspBoehm.c - Implements Boehm single knot insertion routine.              *
  3. * Based on:                                      *
  4. * "Recursive proof of Boehm's knot insertion technique", by Phillip J Barry   *
  5. * Ronald N Goldman, CAD, Volume 20 number 4 1988, pp 181-182.              *
  6. * The original paper by Boehm W. is also sighted there.                  *
  7. *******************************************************************************
  8. * Written by Gershon Elber, Aug. 90.                          *
  9. ******************************************************************************/
  10.  
  11. #include <ctype.h>
  12. #include <stdio.h>
  13. #include <string.h>
  14. #include "cagd_loc.h"
  15.  
  16. /******************************************************************************
  17. * Returns a new curve refined at t (t is inserted as a new knot in Crv).      *
  18. * If however the multiplicity of t in the current knot vector is equal          *
  19. * (or greater!?) to the degree or t is not in the curve parametric domain, no *
  20. * new knot is insert and NULL is returned instead.                  *
  21. * Control mesh is updated as follows (P is old ctl polygon, Q is new):          *
  22. * Let Index be the last knot in old knot vector less than t and              *
  23. * let j be j = Index - order + 1. Also let k be the curve order.          *
  24. *                                          *
  25. *  Case 1: Q(i) = P(i), i <= j                              *
  26. *                                          *
  27. *          t     -    t(i)        t(i+k-1)  -   t              *
  28. *  case 2: Q(i) = --------------- P(i) + --------------- P(i-1), j<i<=Index   *
  29. *          t(i+k-1) - t(i)        t(i+k-1) - t(i)              *
  30. *                                          *
  31. *  case 3: Q(i) = P(i-1), Index < i                          *
  32. *                                          *
  33. *  Note: Altough works, this is not the optimal way to insert many knot!      *
  34. ******************************************************************************/
  35. CagdCrvStruct *BspCrvKnotInsert(CagdCrvStruct *Crv, CagdRType t)
  36. {
  37.     CagdBType
  38.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
  39.     CagdRType
  40.     *KnotVector = Crv -> KnotVector;
  41.     int i, j,
  42.     k = Crv -> Order,
  43.     Len = Crv -> Length,
  44.     KVLen = k + Len,
  45.     Index = BspKnotLastIndexL(KnotVector, KVLen, t),
  46.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  47.     CagdCrvStruct
  48.     *RefinedCrv = CagdCrvNew(Crv -> GType, Crv -> PType, Len + 1);
  49.     CagdRType
  50.     **Points = Crv -> Points,
  51.     **NewPoints = RefinedCrv -> Points;
  52.  
  53.     if (!BspKnotParamInDomain(KnotVector, Len, k, t))
  54.     FATAL_ERROR(CAGD_ERR_T_NOT_IN_CRV);
  55.  
  56.     /* Update the rest of the RefinedCrv data structure (easy part). */
  57.     RefinedCrv -> Order = k;
  58.     RefinedCrv -> KnotVector = BspKnotInsertOne(Crv -> KnotVector, k, Len, t);
  59.  
  60.     /* Case 1: Copy all points upto (Index - Order + 1) as is. */
  61.     for (i = IsNotRational; i <= MaxCoord; i++)
  62.     CAGD_GEN_COPY(NewPoints[i], Points[i],
  63.               sizeof(CagdRType) * (Index - k + 2));
  64.  
  65.     /* Case 2: Convex blend of exactly 2 points. */
  66.     for (j = Index - k + 2; j <= Index; j++)
  67.     for (i = IsNotRational; i <= MaxCoord; i++)
  68.         NewPoints[i][j] =
  69.            ((t - KnotVector[j]) * Points[i][j] +
  70.         (KnotVector[j + k - 1] - t) * Points[i][j - 1]) /
  71.                       (KnotVector[j + k - 1] - KnotVector[j]);
  72.  
  73.     /* Case 3: Copy all points upto the end. */
  74.     for (i = IsNotRational; i <= MaxCoord; i++)
  75.     CAGD_GEN_COPY(&NewPoints[i][Index + 1],
  76.               &Points[i][Index],
  77.               sizeof(CagdRType) * (Len - Index));
  78.  
  79.     return RefinedCrv;
  80. }
  81.  
  82. /******************************************************************************
  83. * Returns a new srf refined at t (t is inserted as a new knot in Crv) in Dir. *
  84. ******************************************************************************/
  85. CagdSrfStruct *BspSrfKnotInsert(CagdSrfStruct *BspSrf, CagdSrfDirType Dir,
  86.                                    CagdRType t)
  87. {
  88.     int Row, Col,
  89.     ULength = BspSrf -> ULength,
  90.     VLength = BspSrf -> VLength,
  91.     UOrder = BspSrf -> UOrder,
  92.     VOrder = BspSrf -> VOrder;
  93.     CagdCrvStruct *Crv, *RefCrv;
  94.     CagdSrfStruct
  95.     *RefSrf = NULL;
  96.  
  97.     switch (Dir) {
  98.     case CAGD_CONST_U_DIR:
  99.         RefSrf = BspSrfNew(ULength + 1, VLength, UOrder, VOrder,
  100.                                   BspSrf -> PType);
  101.         IritFree((VoidPtr) RefSrf -> UKnotVector);
  102.         IritFree((VoidPtr) RefSrf -> VKnotVector);
  103.         RefSrf -> VKnotVector = BspKnotCopy(BspSrf -> VKnotVector,
  104.                      BspSrf -> VLength + BspSrf -> VOrder);
  105.  
  106.         for (Row = 0; Row < VLength; Row++) {
  107.         Crv = BspSrfCrvFromMesh(BspSrf, Row, CAGD_CONST_V_DIR);
  108.         RefCrv = BspCrvKnotInsert(Crv, t);
  109.  
  110.         if (Row == 0) {          /* Figure out refined knot vector. */
  111.             RefSrf -> UKnotVector = BspKnotCopy(RefCrv -> KnotVector,
  112.                        RefCrv -> Length + RefCrv -> Order);
  113.         }
  114.  
  115.         CagdCrvToMesh(RefCrv, Row, CAGD_CONST_V_DIR, RefSrf);
  116.  
  117.         CagdCrvFree(Crv);
  118.         CagdCrvFree(RefCrv);
  119.         }
  120.         break;
  121.     case CAGD_CONST_V_DIR:
  122.         RefSrf = BspSrfNew(ULength, VLength + 1, UOrder, VOrder,
  123.                                  BspSrf -> PType);
  124.         IritFree((VoidPtr) RefSrf -> UKnotVector);
  125.         IritFree((VoidPtr) RefSrf -> VKnotVector);
  126.         RefSrf -> UKnotVector = BspKnotCopy(BspSrf -> UKnotVector,
  127.                     BspSrf -> ULength + BspSrf -> UOrder);
  128.  
  129.         for (Col = 0; Col < ULength; Col++) {
  130.         Crv = BspSrfCrvFromMesh(BspSrf, Col, CAGD_CONST_U_DIR);
  131.         RefCrv = BspCrvKnotInsert(Crv, t);
  132.  
  133.         if (Col == 0) {          /* Figure out refined knot vector. */
  134.             RefSrf -> VKnotVector = BspKnotCopy(RefCrv -> KnotVector,
  135.                        RefCrv -> Length + RefCrv -> Order);
  136.         }
  137.  
  138.         CagdCrvToMesh(RefCrv, Col, CAGD_CONST_U_DIR, RefSrf);
  139.  
  140.         CagdCrvFree(Crv);
  141.         CagdCrvFree(RefCrv);
  142.         }
  143.         break;
  144.     default:
  145.         FATAL_ERROR(CAGD_ERR_DIR_NOT_CONST_UV);
  146.         break;
  147.     }
  148.  
  149.     return RefSrf;
  150. }
  151.